package org.liaohailong.helloworld.study;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Stack;

/**
 * Author: liaohailong
 * Time: 2021/5/10 13:30
 * Describe:
 */
public class ReservePolish {

    /**
     * 计算逆波兰表达式
     */
    public int calculate(String[] token) {
        Stack<Integer> stack = new Stack<>();

        for (String str : token) {
            if (isNumber(str)) {
                stack.push(Integer.parseInt(str));
            } else {
                int t2 = stack.pop();
                int t1 = stack.pop();
                int res = doOp(t1, t2, str);
                stack.push(res);
            }
        }

        return stack.pop();
    }


    /**
     * 算术表达式转换成逆波兰表达式
     */
    public String[] parse(String str) {
        // 移除所有空格
        str = str.replaceAll(" ", "");

        Map<String, Integer> priority = new HashMap<>();
        priority.put("(", 0);
        priority.put("+", 1);
        priority.put("-", 1);
        priority.put("*", 2);
        priority.put("/", 2);

        Stack<String> stack = new Stack<>();
        LinkedList<String> token = new LinkedList<>();

        for (int i = 0; i < str.length(); i++) {
            String one = String.valueOf(str.charAt(i));
            if (isOp(one, true)) {

                // 遇到左括号直接入栈
                if ("(".equals(one)) {
                    stack.push(one);
                    continue;
                }

                // 遇到右括号，把站内所有符号出栈，直到遇到左括号，并且左括号出栈
                if (")".equals(one)) {
                    while (!"(".equals(stack.peek())) token.addLast(stack.pop());
                    stack.pop();// 左括号出栈
                    continue;
                }

                /*
                 * 两种特殊情况：
                 * 1，表达式以负数开头
                 * 2，*或/ 之后接一个负数
                 * */
                if (token.isEmpty()) {
                    // 负号开头，检索数字
                    int beginIndex = i;
                    int endIndex = find(str, beginIndex);
                    String number = str.substring(i, endIndex + 1);
                    token.addLast(number);
                    i = endIndex;
                } else {
                    // 第一个操作符号入栈
                    if (stack.isEmpty()) {
                        stack.push(one);
                    } else {
                        // 上一个是操作符，需要取出整块的负数多位数
                        String lastOne = String.valueOf(str.charAt(i - 1));
                        boolean op = isOp(lastOne, false);
                        if (op) {
                            // 负号开头，检索数字
                            int beginIndex = i;
                            int endIndex = find(str, beginIndex);
                            String number = str.substring(i, endIndex + 1);
                            token.addLast(number);
                            i = endIndex;
                        } else {
                            String top = stack.peek();
                            int p1 = priority.get(one);
                            int p2 = priority.get(top);
                            // 本操作符号的优先级高于栈顶，直接入栈
                            if (p1 > p2) {
                                stack.push(one);
                            } else {
                                // 本操作符号优先级小于等于栈顶，栈顶符号出栈，继续比较新栈顶，完了之后本操作符号入栈
                                do {
                                    top = stack.pop();
                                    token.addLast(top);
                                    if (stack.isEmpty()) {
                                        break;
                                    }
                                    top = stack.peek();
                                    p2 = priority.get(top);
                                } while (p1 <= p2);
                                stack.push(one);
                            }
                        }
                    }
                }
            } else {
                // 考虑多位数
                int beginIndex = i;
                int endIndex = find(str, beginIndex);
                String number = str.substring(i, endIndex + 1);
                token.addLast(number);
                i = endIndex;
            }
        }

        // 加入站内所有剩余操作符号
        while (!stack.isEmpty()) token.add(stack.pop());

        return token.toArray(new String[]{});
    }

    /**
     * 寻找多位数
     *
     * @param str        总字符串
     * @param beginIndex 开始寻找的位置，这个位置不包括，从它的下一个开始，因为这个位置应该是个"-"号
     * @return 连续的数字 -> 多位数
     */
    private int find(String str, int beginIndex) {
        int endIndex = beginIndex;
        for (int i = beginIndex + 1; i < str.length(); i++) {
            String s = String.valueOf(str.charAt(i));
            if (isNumber(s)) {
                endIndex = i;
                continue;
            }
            break;
        }
        return endIndex;
    }

    private boolean isNumber(String str) {
        return !isOp(str, true);
    }

    /**
     * 是否是操作运算符
     *
     * @param str     符号检索
     * @param include true表示"("和")"也算入操作运算符
     * @return true表示改字符是操作运算符
     */
    private boolean isOp(String str, boolean include) {
        boolean ok = false;
        switch (str) {
            case "+":
            case "-":
            case "*":
            case "/":
                ok = true;
                break;
        }
        if (include) {
            switch (str) {
                case "(":
                case ")":
                    ok = true;
                    break;
            }
        }
        return ok;
    }

    private int doOp(int t1, int t2, String op) {
        int res = 0;
        switch (op) {
            case "+":
                res = t1 + t2;
                break;
            case "-":
                res = t1 - t2;
                break;
            case "*":
                res = t1 * t2;
                break;
            case "/":
                res = t1 / t2;
                break;
        }

        return res;
    }
}
